<html>
<head>
  <title>动态规划</title>
  <basefont face="微软雅黑" size="2" />
  <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
  <meta name="exporter-version" content="Evernote Windows/307027 (zh-CN, DDL); Windows/6.1.0 (Win32);"/>
  <style>
    body, td {
      font-family: 微软雅黑;
      font-size: 10pt;
    }
  </style>
</head>
<body>
<a name="604"/>
<h1>动态规划</h1>

<div>
<span><div><div><span style="-en-paragraph: true; color: #ff0000; font-size: 18px; font-family: SimSun; font-weight: bold;">递归到动规的一般转化方法</span></div><div><span style="-en-paragraph: true; font-family: SimSun; font-size: 18px;">    递归函数有n个参数，就定义一个n维的数组，数组的下标是递归函数参数的取值范围，数组元素的值是递归函数的返回值，这样就可以从边界值开始， 逐步填充数组，相当于计算递归函数值的逆过程。</span></div><div><br/></div><div><span style="color: #ff0000; font-size: 18px; font-family: SimSun; font-weight: bold;">动规解题的一般思路</span></div><div><span style="-en-paragraph: true; color: #000000; font-size: 18px; font-family: SimSun; font-weight: bold;">1. 将原问题分解为子问题</span></div><ul><li><span style="font-family: SimSun; font-size: 18px;"> 把原问题分解为若干个子问题，子问题和原问题形式相同或类似，只不过规模变小了。子问题都解决，原问题即解决(数字三角形例）。</span></li><li><span style="font-family: SimSun; font-size: 18px;"> 子问题的解一旦求出就会被保存，所以每个子问题只需求 解一次。</span></li></ul><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-weight: bold; font-family: SimSun; font-size: 18px;">    2.确定状态</span></div><ul><li><span style="font-family: SimSun; font-size: 18px;"> 在用动态规划解题时，我们往往将和子问题相关的各个变量的一组取值，称之为一个“状 态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状 态”所对应的子问题的解。</span></li><li><span style="font-family: SimSun; font-size: 18px;"> 所有“状态”的集合，构成问题的“状态空间”。“状态空间”的大小，与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里，一共有N×(N+1)/2个数字，所以这个问题的状态空间里一共就有N×(N+1)/2个状态。</span></li></ul><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-family: SimSun; font-size: 18px;">    整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个“状态”只需要经过一次，且在每个状态上作计算所花的时间都是和N无关的常数。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-size: 18px; font-family: SimSun; font-weight: bold;">    3.确定一些初始状态（边界状态）的值</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-family: SimSun; font-size: 18px;">    以“数字三角形”为例，初始状态就是底边数字，值就是底边数字值。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-size: 18px; font-family: SimSun; font-weight: bold;">    4. 确定状态转移方程</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-family: SimSun; font-size: 18px;">     定义出什么是“状态”，以及在该“状态”下的“值”后，就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”，求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。</span></div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="font-family: SimSun; font-size: 18px; line-height: 1.45;"><span>    </span> 数字三角形的状态转移方程:</span></div><div>    <img src="动态规划_files/Image.png" type="image/png" data-filename="Image.png"/></div><div><span style="-en-paragraph: true;"> </span></div><div><br/></div><div><span style="font-weight: bold; font-family: SimSun; font-size: 18px;"><font style="color: rgb(227, 0, 0);">能用动规解决的问题的特点</font></span></div><div><br/></div><div><span style="-en-paragraph: true; font-family: SimSun; font-size: 18px;"><span>    </span>1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的，我们就称该问题具有最优子结 构性质。</span></div><div><span style="-en-paragraph: true; font-family: SimSun; font-size: 18px;">    2) 无后效性。当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态，没有关系。</span></div><div><br/></div><div><br/></div><div><font style="font-size: 18pt; color: rgb(173, 0, 0);"><b>动态规划的本质，是对问题<span style="font-style: italic;">状态的定义</span>和<span style="font-style: italic;">状态转移方程</span>的定义。</b></font></div><div><br/></div><div>动态规划是通过<span style="font-weight: bold;">拆分问题，</span>定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。</div><div>本题下的其他答案，大多都是在说递推的求解方法，但<span style="font-weight: bold;">如何拆分问题</span>，才是动态规划的核心。</div><div>而<span style="font-weight: bold;"><font style="font-size: 12pt; color: rgb(173, 0, 0);">拆分问题</font></span>，靠的就是<span style="font-weight: bold; font-style: italic;"><font style="font-size: 12pt; color: rgb(227, 0, 0);">状态的定义</font></span>和<font style="font-size: 12pt; color: rgb(227, 0, 0);"><span style="font-weight: bold; font-style: italic;">状态转移方程</span><span style="font-weight: bold;">的定义</span></font>。</div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><span style="font-weight: bold;"><font style="font-size: 18pt; color: rgb(28, 51, 135);">状态的定义？</font></span></div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">给定一个数列，长度为N，</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">求这个数列的最长上升（递增）子数列（LIS）的长度.</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">以</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">1 7 2 8 3 4</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">为例。</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">这个数列的最长递增子数列是 1 2 3 4，长度为4；</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">次长的长度为3， 包括 1 7 8; 1 2 3 等.</span></div></div><div>要解决这个问题，我们首先要<span style="font-weight: bold;">定义这个问题</span>和这个问题的子问题。</div><div>有人可能会问了，题目都已经在这了，我们还需定义这个问题吗？需要，原因就是这个问题在字面上看，找不出子问题，而没有子问题，这个题目就没办法解决。</div><div>所以我们来重新定义这个问题：</div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">给定一个数列，长度为N，</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">设</span><img src="https://www.zhihu.com/equation?tex=F_%7Bk%7D" style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"></img><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">为：以数列中第k项结尾的最长递增子序列的长度.</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">求</span><img src="https://www.zhihu.com/equation?tex=F_%7B1%7D..F_%7BN%7D" style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"></img> <span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">中的最大值.</span></div></div><div>而对于<img src="https://www.zhihu.com/equation?tex=F_%7Bk%7D"></img>来讲，<img src="https://www.zhihu.com/equation?tex=F_%7B1%7D+..+F_%7Bk-1%7D"></img>都是<img src="https://www.zhihu.com/equation?tex=F_%7Bk%7D"></img>的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第<img src="https://www.zhihu.com/equation?tex=1..k-1"></img>中某项结尾的LIS。</div><div style="box-sizing: border-box; padding: 8px; font-family: Monaco, Menlo, Consolas, &quot;Courier New&quot;, monospace; font-size: 12px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; background-color: rgb(251, 250, 248); border: 1px solid rgba(0, 0, 0, 0.14902); background-position: initial initial; background-repeat: initial initial;-en-codeblock:true;"><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">给定一个数列，长度为N，</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">设</span><img src="https://www.zhihu.com/equation?tex=F_%7Bi%2C+k%7D" style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"></img><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">为：</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">在前i项中的，长度为k的最长递增子序列中，最后一位的最小值.</span> <img src="https://www.zhihu.com/equation?tex=1%5Cleq+k%5Cleq+N" style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"></img><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">.</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">若在前i项中，不存在长度为k的最长递增子序列，则</span><img src="https://www.zhihu.com/equation?tex=F_%7Bi%2C+k%7D" style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"></img><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">为正无穷.</span></div><div><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">求最大的x，使得</span><img src="https://www.zhihu.com/equation?tex=F_%7BN%2Cx%7D" style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);"></img><span style="font-family: Monaco; font-size: 9pt; color: rgb(51, 51, 51);">不为正无穷。</span></div></div><div>上述的<img src="https://www.zhihu.com/equation?tex=F_%7Bi%2C+k%7D"></img>就是状态，定义中的“<img src="https://www.zhihu.com/equation?tex=F_%7Bi%2C+k%7D"></img>为：在前i项中，长度为k的最长递增子序列中，最后一位的最小值”就是对状态的定义。</div><div><br/></div><div><br/></div><div><br/></div><div><font style="font-size: 18pt; color: rgb(28, 51, 135);"><b>状态转移方程？</b></font></div><div><span>上述状态定义好之后，状态和状态之间的关系式，就叫做</span><span>状态转移方程。</span></div><div>比如，对于LIS问题，我们的第一种定义：</div><blockquote><div>设<img src="https://www.zhihu.com/equation?tex=F_%7Bk%7D"></img>为：以数列中第k项结尾的最长递增子序列的长度.</div></blockquote><div>设A为题中数列，状态转移方程为：</div><blockquote><div><img src="https://www.zhihu.com/equation?tex=F_%7B1%7D+%3D+1"></img> （根据状态定义导出边界情况）</div><div><img src="https://www.zhihu.com/equation?tex=F_%7Bk%7D%3Dmax%28F_%7Bi%7D%2B1+%7C+A_%7Bk%7D%3EA_%7Bi%7D%2C+i%5Cin+%281..k-1%29%29+"></img><img src="https://www.zhihu.com/equation?tex=%28k%3E1%29"></img></div></blockquote><div>用文字解释一下是：</div><div><span>以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。</span></div><div><br/></div><div><br/></div><div><br/></div><div><span style="font-weight: bold;"><font style="font-size: 18pt; color: rgb(28, 51, 135);">动态规划迷思</font></span></div><div>a. “缓存”，“重叠子问题”，“记忆化”：</div><div>这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算<span style="text-decoration: underline;">第99项</span>和98项；在计算第101项的时候，需要第100项和<span style="text-decoration: underline;">第99项</span>，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。</div><div>上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。<span style="font-weight: bold;">都不是动态规划的本质，</span><span style="font-weight: bold;">不是动态规划的核心。</span></div><div><br/></div><div>b. “递归”：</div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">递归是递推式求解的方法，连技巧都算不上。</span></div><div>c. &quot;无后效性&quot;，“最优子结构”：</div><div>上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是&quot;无后效性&quot;的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。</div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true; font-weight: bold;">在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。对状态和“最优子结构”的关系的进一步解释，</span><a href="http://www.zhihu.com/question/23995189/answer/35429905" style="-en-paragraph: true; font-weight: bold;">什么是动态规划？动态规划的意义是什么？ - 王勐的回答</a> <span style="-en-paragraph: true; font-weight: bold;">写的很好，大家可以去读一下。</span></div><div>需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，<span style="font-style: italic; font-weight: bold;">不代表该问题不适用动态规划</span>。这也是其他几个答案中出现的逻辑误区：</div><div style="-en-paragraph: true; margin-top: 1em; margin-bottom: 1em;"><span style="-en-paragraph: true;">动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义</span><span style="-en-paragraph: true; font-weight: bold;">，</span><span style="-en-paragraph: true;">在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。</span></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div><div><br/></div></div></span>
</div></body></html> 